/**
 * Created by L.jp
 * Description:给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 * 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 *
 * 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 * User: 86189
 * Date: 2022-02-12
 * Time: 19:35
 */
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    /*  排序链表最好使用归并排序，原理就是对数组归并排序，
        递归的归并排序时间复杂度的O(n*logn),空间复杂度是O（N)
        递归的也叫作自顶向下的排序，也就是从链表两头开始，找到中间点，然后分成两个子链表，然后再找子链表的中间点
        就这样依次类推，直到最后每个子链表只剩下一个节点，然后递的过程结束开始归，归的过程就是依次对子链表升序排序，过程就是合并

        要使空间复杂度更高的话那就使用迭代版本，也就做自底向上的方法，也就是从一开始以一个节点为一组开始
        然后组里的元素按2倍的形式增长，第二次就是两个元素为一组，排序的过程中就合并，然后组别元素再以2倍增长
        直到组别元素大于等于原来链表的长度，此时就排序完成
    *
    * */
    public ListNode sortList(ListNode head) {
        //递归版本
        if(head==null || head.next==null){
            return head;
        }
        //接下来不断递归找中间节点，直到最后只剩一个节点
        //这里解释下为什么对于链表排序找中间节点要让快指针先走一步在慢指针之前，因为我们在其他的找中间节点都是快慢指针
        //在同一起点，然后快指针走两步，慢指针走一步这样走，但是对于这个排序链表题，我们递归就是要让每一个点作为断开两个链表的中间节点
        //对于数组归并排序我们只需要记录每一个中间节点，然后作为下一次分割的界点，但是对于链表我们找中间节点是需要快慢指针的
        //如果每次找到中间节点之后，不断开指向，那么就永远找不到中间节点，陷入死循环
        //对于这个链表题，我们找到中间节点就是每一次的慢指针的位置，首先我们要保存他的下一个节点，作为右边子链表的头节点
        //然后我们要断开慢指针的下一步指向，使得下一次快指针的结尾就是当前这个位置，这样才能找到中间节点

        //那么为什么这个快指针要在慢指针前一步，因为我们可以想到当只有两个节点的链表时，我们应该分割成两个节点作为两个子链表
        //如果我们是快慢指针在同一起点，然后再按照快的走两步，慢的走一步这个方法的话，那么slow永远停在的就是第二个节点的位置
        //然后它后面已经是空了，就断开也这样，然后下一次递归找中间节点的结果还是这样，始终无法分割开第一个节点，造成栈溢出
        //但是两个节点时，我们如果让快指针在慢指针前面一步，那么快指针就走不了，进不去while循环，然后就可以找到第二个子链表的头结点就是慢指针的下一个节点
        //同时也可以将第一个节点的next域置空，使得第一个节点与第二个节点分开成功，不会栈溢出
        ListNode fast=head.next;
        ListNode slow=head;
        while(fast!=null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //找到了链表中间点就是slow停在的位置
        //应该分割成两个子链表，然后继续找中间点分割链表
        ListNode tmp=slow.next;//下一次的分割子链表的右边头节点
        slow.next = null;//需要切断链表才是分割,使得每一个节点都是独立的节点，如果不断开原有的指向那么在合并链表的时候指向就会是乱的
        //分割子链表
        ListNode left_mid=sortList(head); //head是左边子链表的头节点
        ListNode right_mid=sortList(tmp); //tmp是右边子链表的头结点
        return  mergeList(left_mid,right_mid);
    }
    private ListNode mergeList(ListNode left_mid,ListNode right_mid ) {
        //合并子链表。原理和合并子数组一样，合并中排序
        //需要一个新的头节点构造新的排好序的链表
        ListNode newH=new ListNode(0);
        ListNode cur=newH;
        while(left_mid != null && right_mid != null){
            if(left_mid.val< right_mid.val){
                cur.next=left_mid;
                cur=cur.next;
                left_mid=left_mid.next;
            }else{
                cur.next = right_mid;
                cur = cur.next;
                right_mid=right_mid.next;
            }
        }
        if(left_mid==null){
            cur.next=right_mid;
        }
        if(right_mid == null){
            cur.next = left_mid;
        }
        return newH.next;

    }

}
